package com.zzy.algorithm.sort;

/**
 * 希尔排序
 */
public class Q29_ShellSort {

    public static int[] nums = new int[]{5,7,1,2,8,9,3};

    public static void main(String[] args) {
        shellSort(nums);
        for(int x : nums){
            System.out.println(x);
        }
    }



    private static void shellSort(int[] nums){
        int len = nums.length;
        int gap = len / 2;
        while (gap > 0){
            for(int i = 0; i + gap < len ; i = i + gap){
                int sortNum = nums[i + gap];
                int currentIndex = i;
                while(currentIndex >= 0 && sortNum < nums[currentIndex]){
                    nums[currentIndex + gap] = nums[currentIndex];
                    currentIndex -= gap;
                }
                nums[currentIndex + gap] = sortNum;
            }
            gap /= 2;
        }
    }

}
